// Copyright (c) 2009 Jonathan Traugott & Christopher Keith (chris.keith@gmail.com)
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.

//	various assignments

NOTE THAT THIS WILL NOT COMPILE...
Since I have removed all code from the text book
to comply with Course Technology copyright.
(D. S. Malik "Data Structures Using C++")

#include <stack>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cassert>

using namespace std;

template<class elemType>
class orderedArrayListType: public arrayListType<elemType>
{
public:
  // code removed
  int recursiveBinarySearch(const elemType & val); // *****
  int sequentialSearch(const elemType & val, int* nComparisons); // *****
  int binarySearch(int item, int* nComparisons, bool switchSearch); // *****
private:
  int recursiveBinarySearchHelper(const elemType & val, elemType* array, int size); // *****

};

template<class elemType>
int orderedArrayListType<elemType>::recursiveBinarySearchHelper(const elemType & val, elemType* array, int size) {
	int	ret;
	if (size == 0) {
		ret = -1;
	} else if (size == 1) {
		if (val == array[0]) {
			ret = 0;
		} else {
			ret = -1;
		}
	} else {
		int mid = array[size / 2 - 1];
		if (val == mid) {
			ret = size / 2 - 1;
		} else if (val < mid) {
			ret = recursiveBinarySearchHelper(val, array, size / 2);
		} else {
			ret = recursiveBinarySearchHelper(val, &array[size / 2], size - (size / 2));
			if (ret != -1) {
				ret += size / 2;
			}
		}
	}
	return ret;
}

template<class elemType>
int orderedArrayListType<elemType>::recursiveBinarySearch(const elemType & val) {
  return recursiveBinarySearchHelper(val, list, length);
}

template<class elemType>
int orderedArrayListType<elemType>::sequentialSearch(const elemType & val, int* nComparisons) {
	for (int i = 0; i < length; i++) {
		if (val == list[i]) {
			(*nComparisons)++;
			return i;
		}
		if (val < list[i]) {
			(*nComparisons)++;
			return -1;
		}
	}
	return -1;
}

void doTest(int* vals, int valSize, int* intArray, int arraySize) {
  orderedArrayListType<int>   array;
  for (int i = 0; i < arraySize; i++) {
    array.insertOrd(intArray[i]);
  }
	array.print();
	for (int i = 0; i < valSize; i++) {
		cout << "Value: " << vals[i] << " is at index: " << array.recursiveBinarySearch(vals[i]) << endl; 
	}
}

void doTest2(int* vals, int valSize, int* intArray, int arraySize) {
  orderedArrayListType<int>   array;
  for (int i = 0; i < arraySize; i++) {
    array.insertOrd(intArray[i]);
  }
	array.print();
	for (int i = 0; i < valSize; i++) {
		int nComparisons = 0;
		cout << "Value: " << vals[i] << " is at index: " 
			<< array.sequentialSearch(vals[i], &nComparisons) << endl; 
	}
}

void exercise2() {
  cout << "Exercise 2 (Recursive binary search)" << endl;
	int a[] = { -999, -45, 0, 1, 6, 20, 12345 };
	int v[] = { -999, 1, 20, 2, -10000, 9999999, 12345 };
	doTest(v, sizeof(v) / sizeof(int), a, sizeof(a) / sizeof(int));
	int c[] = { -45, 0, 1, 6, 20, 12345 };
	doTest(v, sizeof(v) / sizeof(int), c, sizeof(c) / sizeof(int));
	cout << endl;
}

void autoTest2() {
	cout << "Sequential search over sorted list: " << endl;
	int a[] = { -999, -45, 0, 1, 6, 20, 20, 12345 };
	int v[] = { -999, 1, 20, 2, -10000, 9999999, 12345 };
	doTest2(v, sizeof(v) / sizeof(int), a, sizeof(a) / sizeof(int));
	int c[] = { -45, 0, 1, 6, 20, 20, 12345 };
	doTest2(v, sizeof(v) / sizeof(int), c, sizeof(c) / sizeof(int));
	cout << endl;
}


// exercise 4, page 557 -------------------------------------------------------------------------
void ex4Test(int* vals, int valSize, orderedArrayListType<int> & array, bool switchSearch) {
	for (int i = 0; i < valSize; i++) {
		int	nComparisons = 0;
		int ret = array.binarySearch(vals[i], &nComparisons, switchSearch);
		cout << "Value: " << vals[i] << ", nComparisons: " << nComparisons;
		if (ret != -1) {
			cout << ", ret: " << ret;
		}
		cout << endl;
	}
}

void ex4TestInt(int* vals, int valSize, int* intArray, int size, bool switchSearch) {
  orderedArrayListType<int>   array;
	for (int i = 0; i < size; i++) {
		array.insertOrd(intArray[i]);
	}
  ex4Test(vals, valSize, array, switchSearch);
}

void smallTest() {
	int a[] = { -999, -45, 0, 1, 6, 20, 20, 12345 };
	int v[] = { -999, 1, 20, 2, -10000, 9999999, 12345 };
	ex4TestInt(v, sizeof(v) / sizeof(int), a, sizeof(a) / sizeof(int), false);
	int c[] = { -45, 0, 1, 6, 20, 20, 12345 };
	ex4TestInt(v, sizeof(v) / sizeof(int), c, sizeof(c) / sizeof(int), false);
	cout << endl;
}

void randTest(int size, bool switchSearch) {
	cout << "Array of size: " << size << endl;
	cout << "SwitchSearch: " << switchSearch << endl;
  orderedArrayListType<int>   array(size + 1);
  int i = 0;
	while (i < size) {
    int r = rand();
    if ( array.binarySearch(r) == -1) {
		  array.insertOrd(r);
      i++;
    }
	}
	if (size <= 10) array.print();
	int	vals[5];
	array.retrieveAt(0, vals[0]);
  vals[0]--;
	array.retrieveAt(0, vals[1]);
	array.retrieveAt(size / 2, vals[2]);
	array.retrieveAt(size - 1, vals[3]);
	array.retrieveAt(size / 2, vals[4]);
	vals[4]++;
	ex4Test(vals, 5, array, switchSearch);
}

void exercise4() {
	cout << "Exercise 4 (add sequential search)" << endl;
	// smallTest(); // for debugging only
	randTest(1000, false);
	randTest(1000, true);
	cout << endl;
}

template<class elemType>
class hashT
{
// code removed...
	int findIndex(int hashIndex, const elemType& rec); // *****
};

template <class elemType>
int hashT<elemType>::findIndex(int hashIndex, const elemType& rec) 
{
	int pCount;
	int inc;

	pCount = 0;
	inc = 1;

	while(indexStatusList[hashIndex] == 1
		  && HTable[hashIndex] != rec 
		  && pCount < HTSize / 2)
	{
		pCount++;
		hashIndex = (hashIndex + inc) % HTSize;
		inc += 2;
	}
	return hashIndex;
}

template <class elemType>
void hashT<elemType>::insert(int hashIndex, const elemType& rec)
{
	hashIndex = findIndex(hashIndex, rec);
	if(indexStatusList[hashIndex] != 1)
	{
		HTable[hashIndex] = rec;
		indexStatusList[hashIndex] = 1;
		length++;
	}
	else
		if(HTable[hashIndex] == rec)
			cerr<<"Error: No duplicates are allowed."<<endl;
		else
			cerr<<"Error: The table is full. "
			    <<"Unable to resolve the collision."<<endl;
}
template <class elemType>
void hashT<elemType>::remove(int hashIndex, const elemType& rec)
{
	hashIndex = findIndex(hashIndex, rec);
  if (indexStatusList[hashIndex] != 1) {
    cout << "Unable to find: " << rec << endl;
  } else {
    indexStatusList[hashIndex] = 0;
  }
}


// stupid hash function, but easy to test.
int hashInt(int val) {
	return val % 100;
}

void searchFor(hashT<int> & testH, int val) {
	bool found;
	int		i = hashInt(val * 10);
	testH.search(i, val * 10, found);
	if (found) {
		cout << "found: " << val * 10 << " at index: " << i;
	} else {
		cout << "not found: " << val * 10;
	}
	cout << endl;
}

void isItemAt(hashT<int> & testH, int index, int val) {
	cout << "Item: " << val << " isItemAtEqual is: ";
	if (testH.isItemAtEqual(index, val)) {
		cout << "true";
	} else {
		cout << "false";
	}
	cout << endl;
}

void testRetrieve(hashT<int> & testH, int index) {
	int	r = -999999;
  testH.retrieve(index, r);
	cout << "Retrieve at: " << index << " = ";
  if (r == -999999) {
    cout << "No value found!";
  } else {
    cout << r;
  }
  cout << endl;
}

void exercise5() {
  cout << "Exercise 5 (implement methods on class hashT)" << endl;
	hashT<int>	testH;
	for (int i = 0; i < 80; i++) {
		testH.insert(hashInt(i * 10), i * 10);
	}
	// testH.print(); // for debugging only.
	searchFor(testH, -1);
	searchFor(testH, 3);
	searchFor(testH, 70);
	searchFor(testH, 10000);
	isItemAt(testH, 30, 30);
	isItemAt(testH, 700, 70);
	testRetrieve(testH, 30);
	testRetrieve(testH, 36);
  testH.remove(hashInt(30), 30);
  testH.remove(hashInt(30), 30);
	testRetrieve(testH, 30);
  testH.remove(hashInt(36), 36);
}

int main() {
  exercise2();
  exercise4();
	exercise5();
  char ch;
  cin.get(ch);
	return 0;
}
